package labuladong.leetcode.editor.cn._01linkedlist.ch00;

import labuladong.leetcode.editor.cn._00bean.ListNode;

import static labuladong.leetcode.editor.cn._00utils.LinkedListUtils.build;
import static labuladong.leetcode.editor.cn._00utils.LinkedListUtils.print;

public class _876_MiddleOfTheLinkedList {

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode middleNode(ListNode head) {
            // 快慢指针初始化指向 head
            ListNode slow = head, fast = head;
            // 快指针走到末尾时停止
            while (fast != null && fast.next != null) {
                // 慢指针走一步，快指针走两步
                slow = slow.next;
                fast = fast.next.next;
            }
            // 慢指针指向中点
            return slow;
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)
    public static void main(String[] args) {
        Solution solution = new _876_MiddleOfTheLinkedList().new Solution();

        int[] nums1 = {1, 2, 3, 4, 5};
        ListNode link1 = build(nums1);
        print(link1);

        ListNode res = solution.middleNode(link1);
        print(res);
    }
}
